/**************************************************************************
***    
*** Copyright (c) 1995-2000 Regents of the University of California,
***               Andrew E. Caldwell, Andrew B. Kahng and Igor L. Markov
*** Copyright (c) 2000-2002 Regents of the University of Michigan,
***               Saurabh N. Adya and Igor L. Markov
***
***  Contact author(s): abk@cs.ucsd.edu, imarkov@umich.edu
***  Original Affiliation:   UCLA, Computer Science Department,
***                          Los Angeles, CA 90095-1596 USA
***
***  Permission is hereby granted, free of charge, to any person obtaining 
***  a copy of this software and associated documentation files (the
***  "Software"), to deal in the Software without restriction, including
***  without limitation 
***  the rights to use, copy, modify, merge, publish, distribute, sublicense, 
***  and/or sell copies of the Software, and to permit persons to whom the 
***  Software is furnished to do so, subject to the following conditions:
***
***  The above copyright notice and this permission notice shall be included
***  in all copies or substantial portions of the Software.
***
*** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
*** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
*** OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
*** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
*** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
*** OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
*** THE USE OR OTHER DEALINGS IN THE SOFTWARE.
***
***
***************************************************************************/





//! author=" Stefanus Mantik"

#ifndef _BATCHED_1_STEINER_H
#define _BATCHED_1_STEINER_H

#include <vector>
using std::vector;

#include <map>
using std::map;

#include "Geoms/point.h"
#include "geomTreeBase.h"

//: Steiner Minimum Tree
class BatchedI1Steiner
{
    //: Neighbour node
    class Neighbour
    {
      public:
        int       id;
        double    weight;

        Neighbour() : id(-1), weight(DBL_MAX) {}
    };

    //: Node of tree 
    class TreeNode
    {
      public:
        int       parent, id;
        double    weight;

        TreeNode() : parent(-1), id(-1), weight(DBL_MAX) {}
    };

    // Candidate node for spanning 
    class SPCandidate
    {
      public:
        Point  point;
        double saving;

        SPCandidate() : point(), saving(0) {}
        SPCandidate(const Point& p, double s) : point(p), saving(s) {}
        bool operator==(const SPCandidate& y) const
        { return point == y.point && saving == y.saving; }
        bool operator!=(const SPCandidate& y) const
        { return point != y.point || saving != y.saving; }
        bool operator<( const SPCandidate& y) const
        { return saving > y.saving; }
       // the operator<() is reversed because we want to sort in
       // decreasing order where X[i-1] > X[i]
    };
    private:

    vector<Point>     _points;    // all points (real points + steiner points)
    unsigned          _nPoints;   // number of real points
    int               _idNum;
    double            _mstCost;
    double            _steinerCost;
    map<int, TreeNode, std::less<int> >  _tree;

    vector<GeomTreeEdge>  _steinerEdges;

    void findNeighbour(int index, vector<Neighbour>& neighbour);
    // Finds up to four closest neighbours for a node
    // in each quadrant and put the closest one as the first neighbour

    double linearMST(int newPoint, const vector<Neighbour>& neighbour);
    // Updates the MST by connecting the new node with
    // its up to four neighbours in the tree and deleting the longest
    // edge along the induced cycle

    void updateTree(int first, int last);
    // Updates the tree by deleting the longest edge along
    // the cycle generated by adding the new point called by linearMST
 
    void moveUp(int& index, int& PO, int id);
    // Traverse the tree from a bottom node to a up level one

    int resetPO(int first, int last);
    // Trace back to the starting point

    void extractEdges();
    // Converting tree into edges (GeomTreeEdge) 

    double generateMST();
    // Generates MST by adding the new nodes one at a time calling linear_MST

    void generateSteiner();
    // Compute the saving  induced by the steiner points using 
    // linearMST updating scheme

    void printTree();

  public:
    BatchedI1Steiner(const vector<Point>& points);

    double getMSTCost() const { return _mstCost; }
    double getCost() const { return _steinerCost; }
    unsigned getNumSteinerPoints() const
    { return _points.size() - _nPoints - 1; }
    const vector<GeomTreeEdge>& getEdges() const { return _steinerEdges; }

};


#endif
